The present invention relates to a computer program and a method for generating a wire routing pattern, which includes wiring paths between one signal-source terminal, which is referred to as a driver hereinafter, and a plurality of signal-receiving terminals, each of which is referred to as a receiver hereinafter.
In the field of the wiring board or the like, when generating wiring paths between one driver and plural receivers, there is a demand for making the total wiring length smallest possible. On the other hand, there is another demand for making the length of each wiring path headed from the driver to each receiver smallest possible. If the total wiring length is reduced, the stray capacitance of the whole wiring path is reduced to restrain signal deterioration. If the length of a wiring path headed from the driver to the receiver is reduced, the deterioration of a specific signal headed from the driver to the receiver is restrained.
In the field of the interconnection among many terminals, there is known the solution of the minimum Steiner tree, which is one method for generating a wire routing pattern having the smallest total wiring length. In general, if there are many terminals and all possible wiring paths must be considered, a huge amount of calculation is required for generating the optimum solution having the smallest total wiring length. Under such circumstances, it is known that when using the approximate solution of the minimum Steiner tree, the shortest wire routing pattern can be generated relatively easily. How to obtain the approximate solution is disclosed in FIG. 3 of Japanese patent publication JP 62-39024 A (1987), which will be referred to as the first publication hereinafter. According to the disclosure of the first publication, the following operations should be carried out. First, there are selected specific two terminals whose distance between them is smallest among possible terminal pairs, and a virtual path is created between the two terminals. Secondary, there is selected a next terminal that is located closest to the virtual path, and an additional path is created between the next terminal and the virtual path to generate a renewed virtual path. A further next terminal is selected similarly, and the virtual path is renewed similarly, and similar operations are repeated for the remaining terminals to generate finally a wire routing pattern that has approximately the smallest total wiring length. This method is disclosed also in FIG. 5 of Japanese patent publication JP 2005-275780 A (2005), which will be referred to as the second publication hereinafter. The method mentioned above will be referred to as the approximate solution of the minimum Steiner tree hereinafter.
The approximate solution of the minimum Steiner tree is useful for easy generation of the wire routing pattern having the smallest total wiring length. The approximate solution, however, has a problem because the driver and the receivers are treated equally or treated with no distinction. This problem will be explained below. Among wiring paths headed from the driver to the receivers, there can be selected one wiring path that has the greatest path length, noting that the number of the wiring paths is equal to the number of the receivers. The greatest path length between the driver and the relevant receiver will be referred to as the greatest D-R path length hereinafter. It can be assumed that there may exist plural kinds of wire routing patterns that have the same smallest total wiring length, and the patterns may have different greatest D-R path lengths. Since the approximate solution of the minimum Steiner tree is the method for generating only one wire routing pattern that has the smallest total wiring length, the generated wire routing pattern not always has the smallest one of the greatest D-R path lengths among the plural wire routing patterns that have the same smallest total wiring length. In other words, in consideration of also the signal flows headed from the driver to the receivers, it is hard to say that the approximate solution of the minimum Steiner tree is the optimum solution.
On the other hand, there is known another method for generating the optimum routing pattern in consideration of the signal flows headed from the driver to the receivers: the method is disclosed in Japanese patent publication JP 11-167564 A (1999), which will be referred to as the third publication hereinafter. The method uses the concept of “overlapping cost” about wiring paths headed from the driver to the receivers. The method can create a common path so as to make the overlapping cost maximum to generate the optimum routing pattern. The method will be referred to as the maximized overlapping cost method hereinafter. The maximized overlapping cost method can always generate the wire routing pattern that has the shortest wiring path between the driver and each of the receivers. The maximized overlapping cost method, however, may generate disadvantageously, depending on an arrangement of terminals, a wire routing pattern having the total wiring path that is greater than that of the pattern generated by the approximate solution of the minimum Steiner tree. Accordingly, the maximized overlapping cost method not always generate the optimum routing pattern that has the smallest total wiring length.
After all, under some arrangements of terminals, the approximate solution of the minimum Steiner tree may generate the optimum routing pattern that has the smallest total wiring length and also the smallest one of the greatest D-R path length. However, under other arrangements of terminals, the approximate solution of the minimum Steiner tree may not generate the pattern that has the smallest one of the greatest D-R path length. On the other hand, under some arrangements of terminals, the maximized overlapping cost method may generate the optimum routing pattern that has the smallest one of the greatest D-R path length and also the smallest total wiring length. However, under other arrangements of terminals, the maximized overlapping cost method may not generate the pattern has the smallest total wiring length.